/**
 * 3
 *  
 * @Author : roryrywang
 * @DateTime : 24-9-10 下午6:39
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string a, b;
        cin >> a >> b;
        vector<vector<int>> f(a.size() + 1, vector<int>(b.size() + 1, 0));
        for (int i = 0; i <= a.size(); i++) {
            f[i][0] = i;
        }
        for (int i = 0; i <= b.size(); i++) {
            f[0][i] = i;
        }

        for (int i = 1; i <= a.size(); i++) {
            for (int j = 1; j <= b.size(); j++) {
                if (a[i - 1] == b[j - 1]) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1]));
                    f[i][j]++;
                }
            }
        }

        cout << f[a.size()][b.size()] << endl;
    }
}